package edu.hawaii.nearestneighbor.util;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import java.util.TreeMap;

/**
 * Nearest neighbor base system. Implements the nearest neighbor algorithm.
 * 
 * @author Robert Puckett
 * 
 */
public class NNutil {

  /**
   * Private constructor.
   */
  private NNutil() {
    // empty
  }

  public static final double epsilon = .000000001;
  
  /**
   * Calccalculate included vector between two vectorsulates the Euclidean distance between the two
   * DataPoints.
   * 
   * @param p1 Point 1.
   * @param p2 Point 2.
   * @return The Euclidean distance between the two DataPoints.
   */
  public static double euclideanDistance(DataPoint p1, DataPoint p2) {

    double total = 0;
    for (int i = 0; i < p1.x.size(); i++) {
      total = total + Math.pow((p1.x.get(i) - p2.x.get(i)),2.0);
    }

    return Math.abs(Math.sqrt(total));
  }

  /**
   * Calculates the magnitude of the vector (by using Euclidean distance to 0).
   * 
   * @param x The vector of double to have its magnitude calculated.
   * @return The magnitude of the vector x.
   */
  public static double magnitude(List<Double> x) {

    double total = 0.0;
    for (int i = 0; i < x.size(); i++) {
      total = total + ((x.get(i)) * (x.get(i)));
    }

    return Math.sqrt(total);
  }

  /**
   * Finds the k nearest points in data to the test point.
   * 
   * @param data the set of points.
   * @param test the test point to find the nearest neighbors.
   * @param k the number of neighbors to find.
   * @return the list of k datapoints that are closest to test point.
   */
  public static List<DataPoint> findKNearest(List<DataPoint> data, DataPoint test, int k) {
    List<DataPoint> result = new ArrayList<DataPoint>();
    // Try reimplementing this as findmin(k) times, build list of visited already
//    List<Integer> mins = new ArrayList<Integer>();
//    List<Double> distances = new ArrayList<Double>();
//    result.clear();
//    mins.clear();
//    distances.clear();
//    int minIndex = 0;
//    minIndex = 0;
//
//    boolean isFirst = true;
//
//    for (DataPoint c : data) {
//      distances.add(euclideanDistance(c, test));
//    }
//
//    for (int i = 0; i < k; i++) {
//      isFirst = true;
//      for (int j = 0; j < distances.size(); j++) {
//        if (data.get(j) == test) { // want to exclude same point, not just identical points
//          continue;
//        }
//        if (mins.contains(j)) {
//          continue;
//        }
//        if (isFirst) {
//          minIndex = j;
//          isFirst = false;
//        }
//        if (distances.get(j) < distances.get(minIndex)) {
//          minIndex = j;
//        }
//      }
//      mins.add(minIndex);
//    }
//
//    for (Integer c : mins) {
//      result.add(data.get(c));
//    }
    //    
    //    
    //    
     // TreeMap will maintain datapoints in sorted order of their distance (key value)
     TreeMap<Double,DataPoint> dist2point = new TreeMap<Double,DataPoint>();
        
     // Find all of the distances between the test point and the points list.
     for (DataPoint c: data) {
     // Add the associated distance/DataPoint to the treemap sorted by distance
     dist2point.put(euclideanDistance(c,test), c);
     }
     double first = 0.0;
     
     while (result.size() < k) {
     first = dist2point.firstKey();
     if (test == dist2point.get(first)) // want to see if they're the same instance
     {
       dist2point.remove(first);
       continue;
     }
     result.add(dist2point.remove(first));
     }
//    System.out.print("K: ");
//    for (DataPoint c : result) {
//      System.out.print(c.state);
//    }
//    System.out.println();
    return result;
  }

  // public static class Distance implements Comparable<Distance>,Comparator<Distance> {
  // public double dist;
  // public DataPoint point;
  // public Distance(double d, DataPoint c) {
  // dist = d;
  // point = c;
  // }
  // public int compare(Distance arg0, Distance arg1) {
  //      
  // Distance d1 = (Distance)arg0; // If this doesn't work, ClassCastException is thrown
  // Distance d2 = (Distance)arg1; // If this doesn't work, ClassCastException is thrown
  // double result = d1.dist - d2.dist;
  // if (result < 0) {
  // return -1;
  // }
  // if (result > 0) {
  // return 1;
  // }
  // return 0;
  // }
  // public int compareTo(Distance arg0) {
  //  
  // Distance d2 = (Distance)arg0; // If this doesn't work, ClassCastException is thrown
  // double result = this.dist - d2.dist;
  // if (result < 0) {
  // return -1;
  // }
  // if (result > 0) {
  // return 1;
  // }
  // return 0;
  // }
  // public boolean equals( Distance obj ) {
  //      
  // if (this.dist == obj.dist) {
  // return true;
  // }
  // return false;
  // }
  //
  // }
  //  
  // /**
  // * Finds the k nearest points in data to the test point.
  // * @param data the set of points.
  // * @param test the test point to find the nearest neighbors.
  // * @param k the number of neighbors to find.
  // * @return the list of k datapoints that are closest to test point.
  // */
  // public static List<DataPoint> findKNearest(List<DataPoint> data, DataPoint test, int k) {
  // List<DataPoint> result = new ArrayList<DataPoint>();
  //
  // // TreeMap will maintain datapoints in sorted order of their distance (key value)
  //
  // ArrayList<Distance> dist2point = new ArrayList<Distance>();
  //    
  //    
  // // Find all of the distances between the test point and the points list.
  // Distance d;
  // for (DataPoint c: data) {
  // // Add the associated distance/DataPoint to the list sorted by distance
  // d = new Distance(euclideanDistance(c,test), c);
  // dist2point.add(d);
  // }
  //
  // Collections.sort(dist2point);
  //
  // d = null;
  // for (int i = 0; i<k; i++) {
  // d = dist2point.remove(0);
  // result.add(d.point);
  // }
  //    
  // return result;
  // }

  /**
   * Calculates the unit vector (magnitude is 1).
   * 
   * @param u the vector to be normalized.
   * @return the unit vector of u.
   */
  public static List<Double> calcUnitVector(List<Double> u) {
    List<Double> uhat = new ArrayList<Double>();
    double umag = NNutil.magnitude(u);
    for (int j = 0; j < u.size(); j++) {
      uhat.add(u.get(j) / umag);
    }
    if (!epsEqual(NNutil.magnitude(uhat),1.0)) {
      System.out.println(NNutil.magnitude(uhat));
      System.out.println("FAILURE IN UNIT VECTOR CALCULATION! NOT MAGNITUDE 1!");
    }
    return uhat;
  }

  /**
   * Calculates the included angle between the two specified lengths of the triangle.
   * 
   * @param a The positive length of triangle edge BC.
   * @param b The positive length of triangle edge AC
   * @return The included angle C.
   */
  public static double calcIncludedAngle(List<Double> a, List<Double> b) {
    // Included angle = cos^-1 (u \dot v)
//    double angle = Math.acos(NNutil.dotProd(calcUnitVector(a), calcUnitVector(b)));
//    if (angle < 0) {
//      angle = angle * -1; // testing this out!!!!!!!
//    }
    double aMag = NNutil.magnitude(a);
    double bMag = NNutil.magnitude(b);
    double dotProd = NNutil.dotProd(a,b);
    double cosAng = dotProd / (aMag * bMag);
    
    return Math.acos(cosAng);
  }

  /**
   * Calculates the cosine of the included angle between the two specified lengths of the triangle.
   * 
   * @param a The positive length of triangle edge BC.
   * @param b The positive length of triangle edge AC
   * @return The cosine of the included angle.
   */
  public static double cosIncludedAngle(List<Double> a, List<Double> b) {
    // Included angle = cos^-1 (u \dot v)
//    double angle = Math.acos(NNutil.dotProd(calcUnitVector(a), calcUnitVector(b)));
//    if (angle < 0) {
//      angle = angle * -1; // testing this out!!!!!!!
//    }
    double aMag = NNutil.magnitude(a);
    double bMag = NNutil.magnitude(b);
    double dotProd = NNutil.dotProd(a,b);
    double cosAng = dotProd / (aMag * bMag);
   // System.out.println("Angle: " + cosAng);
    return cosAng;
  }
  
  /**
   * Find the state with the most occurences in the list of points.
   * 
   * @param points A set of DataPoints.
   * @return The integer representation of the of a set of DataPoints.
   */
  public static int modeState(List<DataPoint> points) {
    // Stores the unique states and the count of their occurence in the list
    Map<Integer, Integer> mapping = new HashMap<Integer, Integer>();
    for (DataPoint c : points) {
      if (mapping.containsKey(c.state)) {
        mapping.put(c.state, mapping.get(c.state) + 1);
      }
      else {
        mapping.put(c.state, 1);
      }
    }
    // Find the max count
    int maxcount = 0;

    boolean start = true;
    for (Map.Entry<Integer, Integer> c : mapping.entrySet()) {
      if (start) {
        start = false;
        maxcount = c.getValue();
      }
      else {
        if (c.getValue() > maxcount) {
          maxcount = c.getValue();
        }
      }
    }

    List<Integer> maxStates = new ArrayList<Integer>();
    for (Map.Entry<Integer, Integer> c : mapping.entrySet()) {
      if (c.getValue() == maxcount) {
        maxStates.add(c.getKey());
      }
    }

    return maxStates.get((int) (Math.random() * maxStates.size()));
  }

  /**
   * Calculates the datapoint difference.
   * 
   * @param p1 The first data point.
   * @param p2 The second data point.
   * @return The datapoint resulting from p1-p2, discarding class identity.
   */
  public static DataPoint diff(DataPoint p1, DataPoint p2) {
    return new DataPoint(diff(p1.x, p2.x), null);
  }

  /**
   * Calculates the list difference.
   * 
   * @param p1 The first list (minuend).
   * @param p2 The second list (subtrahend).
   * @return The list resulting from p1-p2.
   */
  public static List<Double> diff(List<Double> p1, List<Double> p2) {
    List<Double> result = new ArrayList<Double>();
    for (int i = 0; i < p1.size(); i++) {
      result.add(p1.get(i) - p2.get(i));
    }
    return result;
  }

  /**
   * Calculates the dot product between two vectors.
   * 
   * @param p1 the first vector.
   * @param p2 the second vector.
   * @return the dot product of p1 and p2.
   */
  public static double dotProd(List<Double> p1, List<Double> p2) {
    double sum = 0.0;
    for (int i = 0; i < p1.size(); i++) {
      sum = sum + p1.get(i) * p2.get(i);
    }
    return sum;
  }
  
  
  /**
   * Checks if two real values are approximately equal (within epsilon).
   * @param v1 double value 1.
   * @param v2 double value 2.
   * @return true if v1 is within epsilon of v2.
   */
  public static boolean epsEqual(double v1, double v2) {
    if (Math.abs(v1-v2)<NNutil.epsilon) {
      return true;
    }
    else {
      return false;
    }
  }
  
  
}


